class LRU {
    constructor(opcity) {
        this.opcity = opcity
        this.map = new Map()
        this.node = null
    }

    get(key) {
        // 判断是否存在
        if (this.map.has(key)) {
            // 移动到最前面
            let node = this.map.get(key)
            this.move2start(node)
            return node.val
        }
        return -1

    }
    set(key, value) {
        // 判断是否存在
        if (this.map.has(key)) {
            // 移动到最前面
            let node = this.map.get(key)
            node.val = value
            this.move2start(node)

        }

        // 不存在
        else {

            // 判断是否超过容量
            if (this.map.size >= this.opcity) {
                // 删除最后一个
                let last = this.node.tail
                this.removeNode(last)

            }
            // 创建新节点
            let node = new Node(value)
            this.map.set(key, node)
            this.addNode(node)

        }
    }
    removeNode(node) {
        this.map.delete(node.key)
        node.prev.next = node.next
        node.next.prev = node.prev
    }
    move2start(node) {
        node.prev.next = node.next
        node.next.prev = node.prev
        node.next = this.node
        this.node.prev = node
        node.prev = this.node.prev
        this.node.prev.next = node
        this.node.prev = node
    }
}

class Node {
    constructor(val) {
        this.val = val
        this.head = null
        this.tail = null
        this.prev = null
        this.next = null
    }
}